package a_doubleWrite;

import util.ListNode;
import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author: luolidong
 * @create: 2021-07-23 15:35
 * @version: 1.0
 */
public class L99 {
    TreeNode pre,t1,t2;
    public void recoverTree(TreeNode root) {
        dfs(root);
        //交换值
        int temp=t1.val;
        t1.val=t2.val;
        t2.val=temp;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        if(pre!=null&&pre.val>root.val){
            if(t1==null) t1=pre;
            t2=root;
        }
        pre=root;
        dfs(root.right);
    }

    public static void main(String[] args) {
        L99 l99 = new L99();
        l99.recoverTree(TreeNode.build());
    }
}
